\section{Число элементов}

\subsection*{15}

1) Определим $x \in A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n :$

Пусть $C = A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_{k-1}$, $B = C \bigtriangleup A_k$. В терминах характерестических функций $\chi_{C \bigtriangleup A_k} \equiv \chi_{C} + \chi_{A_k} \pmod{2}$.

Следовательно по индукции $x \in A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n$ - означает, что $x$ принадлежит нечетному кол-ву множеств.\\

2) Рассмотрим $x \in A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n$ в терминах характерестических функций:

Так как  $\rchi_{A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n} = 1$ - только когда $x$ принадлежит нечетному кол-ву множеств. 

\[\implies \rchi_{A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n} = \dfrac{1}{2}[1 - (1 - 2 \rchi_{A_1})(1 - 2 \rchi_{A_2})...(1 - 2 \rchi_{A_n})]\]

Раскрывая скобки: \[\rchi_{A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n} = \sum\limits_{i}\rchi_{A_i} - 2 \sum\limits_{i < j}\rchi_{A_i}\rchi_{A_j} + 4 \sum\limits_{i < j < k}\rchi_{A_i}\rchi_{A_j}\rchi_{A_k} - ...\]

\[\implies |A_1 \bigtriangleup A_2 \bigtriangleup ... \bigtriangleup A_n| = \sum\limits_{i}|A_i| - 2 \sum\limits_{i < j}|A_i \cap A_j| + 4 \sum\limits_{i < j < k}|A_i \cap A_j \cap A_k| - ...\] \hfill $\blacksquare$

\subsection*{16}

Так как в четырехугольнике с тремя белыми вершинами и одной черной всегда можно выделить треугольник с тремя белыми вершинами, и для любого такого треугольника можно выбрать черную точку, значит их поровну

\subsection*{17}

Так как $C_{100}^{57} = C_{100}^{100-57} = C_{100}^{43} \implies$ их поровну

\subsection*{18}
Решение 1:

Так как можно построить биекцию между последовательностями нулей и единиц длинны $n$ и подмножествами $n$-элементного множества, пронумеровав каждый элемент из множества, и сопоставляя всякому $k$-му элементу $1$ если он входит в подмножество, и $0$ если нет. Тем самым мы для всякого подмножества однозначно сопоставили последовательность нулей и единиц, значит их равное количество\\

Решение 2:

Количество последовательностей нулей и единиц длинны $n$. Так как на каждую позицию данной последовательности существует два варианта, что можно на нее поставить, а всего позиций $n$, то всего таких последовательностей $2^n$

Количество подмножеств у $n$-элементного множества, равно количеству возможных неупорядоченных пар из $k$ элементов, при $0 \leq k \leq n$. Всего таких пар $C_n^0 + C_n^1 + ... + C_n^n = (1 + 1)^n = 2^n$

Значит их поровну

\subsection*{19}

Рассмотрим последовательность из нулей и единиц длинны $n$: Количество вариантов расставить $k$ единиц равно $\dfrac{n!}{k!(n-k)!}$

Количество $k$-элементных подмножеств из $n$-элементного множества, это количество вариантов взять неупорядоченную пару из $k$ элементов или $C_n^k = \dfrac{n!}{k!(n-k)!}$

Значит их поровну

\subsection*{20}

\[C_n^k = \dfrac{n!}{k!(n-k)!} = \dfrac{n!}{(n-(n-k))!(n-k)!} = C_n^{n-k}\]

\subsection*{21}

$(1+1)^n = C_n^0 + C_n^1 + ... + C_n^n = 2^n$

\subsection*{22, 23}

1) Рассмотрим $2 \nmid n$:

Так как $C_n^k = C_n^{n-k}$, по условию каждый следующий член меняет знак, так что мы можем разбить сумму на пары $C_n^k - C_n^{n-k}$. И так как каждая такая пара дает $0$, то искомая знакочередующаяся сумма будет давать $0$.

2) Рассмотрим $2 \mid n$:

Каждая пара $C_n^k + C_n^{n-k} = 2 C_n^k$, так что выделяем с каждой пары $2$, кроме члена $m$ такого, что  $m = n-m$, но по условию он и так таков, что $2 \mid C_n^m$. Выносим $2$ за скобки и снова получаем знакочередующийся ряд. Продолжаем такие итерации до полной готовности (пока количество членов не станет нечетным).

Значит $C_n^0 - C_n^1 + ... + (-1)^nC_n^n = 0$

P.s подумайте самостоятельно, какова связь 22 и 23 задач

\subsection*{24}

Так как количество способов взять $a^kb^{n-k}$ из $n$ скобок $(a+b)$, равно количеству неупорядоченных пар из $k$ элементов, что равно $C_n^k \implies$\\ \[(a + b)^n = C_n^0a^n + C_n^1a^{n-1}b + ... + C_n^1ab^{n-1} + C_n^nb^n\]

\subsection*{25}

Решение 1:

Для $n = 0$ - кол-во букв, есть 1 способ расставить скобки

Пусть $C_n$ - количество способов расставить скобки для $n$ элементов. Тогда оно должно удовлетворять условиям $C_n = \sum\limits_{i=0}^{n-1}C_iC_{n-i-1}$ так как когда мы расставляем скобки для $i$ элементов, остается $n-i$ незатронутых элементов для которых мы также можем расставить скобки. Тем самым мы задали рекурсивный способ задания $C_n$.\\

Рассмотрим количество сопобов расставить непересекающиеся диагонали в выпуклом n-угольнике. Пронумеруем все вершины от $1$ до $n$ и зафиксируем "начальную" сторону с вершинами $1$ и $2$. Далее проведем диагональ, таким образом что бы треугольник с вершинами в $1$ и $2$ входили в разбиение. Далее есть два варианта, либо третья вершина это либо $3$, либо $n$ и тогда "отрезается" один треугольник с сохранением разбиения для исходного многоугольника, либо третья вершина одна из $4, 5, ..., n-1$ и тогда многоугольник делится на две части. 
Одна из них разрезается на $k$ треугольников, а другая на $n - k$. При этом $k$ принимает значения от $0$ до $n$. 
Рассуждая по индукции, мы одну часть триангулируем $C_k$ способами, а другую $C_{n-k}$ способами. Тем самым количество таких разбиений равно $C_n = \sum\limits_{i=0}^{n-1}C_iC_{n-i-1}$

\begin{figure}[h]
\includegraphics[scale=0.65]{pic/1.2.25.png}
\centering 
\caption{Триангуляция}  
\label{fig:Рис. 2}
\end{figure}

Значит их равное количество\\

Решение 2:

Разметим стороны n-угольника против часовой стрелки цифрами $x_1, ..., x_n$ и зафиксируем $x_1$ как "начальную". Если какие-то буквы $x_i$ и $x_k$, при $1 < i < k \leq n$ у нас перемножаются, то проводим в многоугольнике линию, отрезающую треугольник, и помечаем её произведением $(x_i...x_k)$. Это произведение можно рассматривать как новую "букву"  участвующую в дальнейших произведениях. Отсюда нетрудно видеть, что каждой расстановке скобок в произведении однозначно ставится в соответствие триангуляция, и наоборот












 
